{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "import cv2\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1 2 3 4 5 6 7 8 9]\n"
     ]
    }
   ],
   "source": [
    "#test kernel flatten()\n",
    "kernel = np.array([[1,2,3],[4,5,6],[7,8,9]])\n",
    "kernel_flatten = kernel.flatten()\n",
    "print(kernel_flatten)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 1, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 5, 6, 6, 7, 7, 7, 8, 8, 8, 9, 9]\n",
      "[1, 1, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 5, 6, 6, 7, 7, 7, 8, 8, 8, 9, 9]\n",
      "[1, 1, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 5, 6, 6, 7, 7, 7, 8, 8, 8, 9, 9]\n",
      "[1, 1, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 5, 6, 6, 7, 7, 7, 8, 8, 8, 9, 9]\n",
      "[1, 1, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 5, 6, 6, 7, 7, 7, 8, 8, 8, 9, 9]\n"
     ]
    }
   ],
   "source": [
    "# test sort algorithm\n",
    "# O(nlog(n)) \n",
    "## Quick Sort  \n",
    "def MyQuickSort(data_list = None):\n",
    "    tmp_list = data_list[:]\n",
    "    N = len(tmp_list)\n",
    "    if N <= 1:\n",
    "        return tmp_list\n",
    "    pivot = tmp_list[0]\n",
    "    return MyQuickSort([x for x in tmp_list[1:] if x < pivot]) + [pivot] + MyQuickSort([x for x in tmp_list[1:] if x >= pivot])\n",
    "\n",
    "alist = [6,7,8,9,3,4,7,8,9,3,1,1,2,3,4,5,6,7,8,4,4,3,2,3]\n",
    "print MyQuickSort(alist)\n",
    "\n",
    "## Merge Sort\n",
    "def Merge(left_list, right_list):\n",
    "    result = []\n",
    "    left_count = 0\n",
    "    right_count = 0\n",
    "    while left_count < len(left_list) and right_count < len(right_list):\n",
    "        if left_list[left_count] < right_list[right_count]:\n",
    "            result.append(left_list[left_count])\n",
    "            left_count += 1\n",
    "        else:\n",
    "            result.append(right_list[right_count])\n",
    "            right_count += 1\n",
    "    if left_count == len(left_list):\n",
    "        for i in right_list[right_count:]:\n",
    "            result.append(i)\n",
    "    else:\n",
    "        for j in left_list[left_count:]:\n",
    "            result.append(j)\n",
    "    return result\n",
    "    \n",
    "def MyMergeSort(data_list = None):\n",
    "    if len(data_list) <= 1:\n",
    "        return data_list\n",
    "    middle = len(data_list) / 2\n",
    "    left_list = MyMergeSort(data_list[:middle])\n",
    "    right_list = MyMergeSort(data_list[middle:])\n",
    "    return Merge(left_list, right_list)\n",
    "    \n",
    "alist = [6,7,8,9,3,4,7,8,9,3,1,1,2,3,4,5,6,7,8,4,4,3,2,3]\n",
    "print MyMergeSort(alist)    \n",
    "    \n",
    "# O(n^2) \n",
    "# Bubble Sort\n",
    "def BubbleSort(data_list = None):\n",
    "    tmp_list = data_list[:]\n",
    "    N = len(tmp_list)\n",
    "    if N <= 1:\n",
    "        return tmp_list\n",
    "    for i in range(0, N-1):\n",
    "        for j in range(0, N - i - 1):\n",
    "            if tmp_list[j] > tmp_list[j + 1]:\n",
    "                tmp_list[j], tmp_list[j + 1] = tmp_list[j + 1], tmp_list[j]\n",
    "    return tmp_list\n",
    "alist = [6,7,8,9,3,4,7,8,9,3,1,1,2,3,4,5,6,7,8,4,4,3,2,3]\n",
    "print BubbleSort(alist) \n",
    "      \n",
    "#Insertion Sort\n",
    "def InsertionSort(data_list = None):\n",
    "    blist = data_list[:]\n",
    "    N = len(blist)\n",
    "    for i in range(0, N - 1):\n",
    "        c = blist[i + 1]\n",
    "        j = i\n",
    "        while j >= 0 and c < blist[j]:\n",
    "            blist[j + 1] = blist[j]\n",
    "            j -= 1\n",
    "        blist[j + 1] = c\n",
    "    return blist\n",
    "alist = [6,7,8,9,3,4,7,8,9,3,1,1,2,3,4,5,6,7,8,4,4,3,2,3]\n",
    "print InsertionSort(alist) \n",
    "    \n",
    "# O(n) \n",
    "# Selection Sort\n",
    "def SelectionSort(data_list = None):\n",
    "    blist = data_list[:]\n",
    "    N = len(blist)\n",
    "    for i in range(0, N - 1):\n",
    "        min = i\n",
    "        for j in range(i + 1, N):\n",
    "            if blist[j] < blist[min]:\n",
    "                min = j\n",
    "        if min <> i:\n",
    "            blist[i], blist[min] = blist[min], blist[i]\n",
    "    return blist\n",
    "alist = [6,7,8,9,3,4,7,8,9,3,1,1,2,3,4,5,6,7,8,4,4,3,2,3]\n",
    "print InsertionSort(alist) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.15"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
